#include<iostream>
#include<vector>
#include<string>

using namespace std;



//回溯综合08：字母大小写全排列（优化）
class Solution1 {
public:
    vector<string>  ret;
    //string tmp;
    vector<string> letterCasePermutation(string s) 
    {
        dfs(s,0);
        return ret;
    }

    void dfs(string& s,int nums)
    {
        if(nums==s.size())
        {
            ret.push_back(s);
            return;
        }

        dfs(s,nums+1);

        if((s[nums]<=90&&s[nums]>=65)||(s[nums]<=122&&s[nums]>=97))
        {
            s[nums]^=32;
            dfs(s,nums+1);
            s[nums]^=32;
        }
    }
};

//回溯综合11：有效的数独（优化）
class Solution11 {
public:
    bool row[9][10]={};
    bool col[9][10]={};
    bool gird[3][3][10]={};
    bool isValidSudoku(vector<vector<char>>& board) 
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    int tmp=board[i][j]-'0';
                    if(!row[i][tmp]&&!col[j][tmp]&&!gird[i/3][j/3][tmp])
                    {
                        row[i][tmp]=true;
                        col[j][tmp]=true;      
                        gird[i/3][j/3][tmp]=true;                  
                    }
                    else
                    {
                        cout<<1;
                        return false;
                    }      
                }
            }
        }
        //return dfs(board);
        return true;
    }

    bool dfs(vector<vector<char>>& board)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]=='.')
                {
                    for(int k=1;k<=9;k++)
                    {
                        if(!row[i][k]&&!col[j][k]&&!gird[i/3][j/3][k])
                        {
                            row[i][k]=true;
                            col[j][k]=true;
                            gird[i/3][j/3][k]=true;
                            board[i][j]=k+'0';
                            if(dfs(board)==true)    
                                return true;
                            row[i][k]=false;
                            col[j][k]=false;
                            gird[i/3][j/3][k]=false;
                            board[i][j]='.';
                        }
                    }
                    cout<<2;
                    return false;
                }
            }
        }
        return true;
    }
};

//回溯综合15：不同路劲III（优化版）
class Solution15 {
public:
    int ret=0;
    int path=0;//记录0的数量
    int a=0;//行
    int b=0;//列
    int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    int uniquePathsIII(vector<vector<int>>& grid) 
    {
        a=grid.size();
        b=grid[0].size();
        int x=0;//记录1的初始坐标;
        int y=0;
        for(int i=0;i<a;i++)
        {
            for(int j=0;j<b;j++)
            {
                if(grid[i][j]==0) path++;
                if(grid[i][j]==1)
                {
                    x=i;y=j;
                }
            }
        }
        //cout<<x<<':'<<y<<':'<<path;
        dfs(grid,x,y,0);
        return ret;
    }
    void dfs(vector<vector<int>>& grid,int i,int j,int nums)
    {
        if(grid[i][j]==2&&nums!=path)
            return;
        if(nums==path&&grid[i][j]==2)
        {
            //cout<<nums;
            ret++;
            return;
        }
        for(auto& it:dirs)
        {
            int x=i+it[0];
            int y=j+it[1];
            if(x>=0&&x<a&&y>=0&&y<b&&(grid[x][y]==0||grid[x][y]==2))
            {
                if(grid[x][y]==0)
                {
                    grid[x][y]=-1;
                    //cout<<x<<":"<<y<<" "; 
                    dfs(grid,x,y,nums+1);
                    grid[x][y]=0;
                }
                else 
                {
                    //cout<<x<<":"<<y<<" "; 
                    dfs(grid,x,y,nums); 

                }  
                                   
            }
        }
    }
};


int main()
{
    return 0;
}